# Python 2.6.4
# Project Euler, Problem 132
# Copyright 2010 Talha Zaman

from mine import sieveprimes
def A(n):
    if (n%10) not in [1, 3, 7, 9]: return 0
    last, digit, num = n%10, 0, 0
    while True:
        num = n*table[last,(11-num%10)%10] + num
        while num%10 == 1: num, digit = num/10, digit+1
        if num == 0: break
    return digit
table = dict()
for i in [1, 3, 7, 9]:
    for j in range(10):
        table[i,(i*j)%10] = j
import psyco
psyco.full()
target = 10**9
primes = sieveprimes(1000000)
count, total = 0, 0
for p in primes:
    if p%40 in [1, 9, 11, 17, 21, 31, 33]:
        if not target%A(p):
            count += 1
            total += p
    if count==40: break
print count, total
